from typing import List

class Solution:
    def __init__(self):
        self.cache = {}

    def _match(self, s, i, words):
        if i in self.cache:
            return self.cache[i]
        if len(s) == i:
            return True
        for w in words:
            if s[i:].startswith(w) and self._match(s, i + len(w), words):
                return True
        self.cache[i] = False
        return False

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        return self._match(s, 0, wordDict)

if __name__ == "__main__":
    s  = Solution()
    print(s.wordBreak("leetcode", ["leet","code"]))
    print(s.wordBreak("applepenapple", ["apple","pen"]))
    print(s.wordBreak("catsandog", ["cats","dog","sand","and","cat"]))
    string = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
    wordDict =["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
    print(s.wordBreak(string, wordDict))
